package com.zfl;

public class NumIslands {

    public static void main(String[] args) {
        char[][] grid = {
                {'1','1','0'},
                {'1','0','0'},
                {'0','0','0'}
        };
        int num = new NumIslands().numIslands(grid);
        System.out.println("num = " + num);
    }
    public int numIslands(char[][] grid) {

        int row = grid.length;
        int col = grid[0].length;

        boolean[][] visited = new boolean[row][col];

        int count=0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j]=='0' || visited[i][j])
                    continue;
                dfs(grid,visited,i,j);
                count++;
            }
        }
        return count;

    }

    private void dfs(char[][] grid, boolean[][] visited, int i, int j) {
        int row = grid.length;
        int col = grid[0].length;

        if (i<0 || i>=row || j<0||j>=col || visited[i][j] || grid[i][j]=='0') {
            return;
        }

        visited[i][j]=true;
        dfs(grid,visited,i-1,j);
        dfs(grid,visited,i,j+1);
        dfs(grid,visited,i+1,j);
        dfs(grid,visited,i,j-1);
    }
}
